import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @ClassName Main
 * @Description TODO
 * @Author dzf
 * @Date 2022/5/25 15:19
 * @Version 1.0
 */
public class Main {
    public static int dw=100;
    public static void main(String[] args) throws IOException {
        boolean flag=true;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] strArr=br.readLine().split(" ");
        int N = Integer.parseInt(strArr[0]); //总钱数
        int m = Integer.parseInt(strArr[1]); //想买得物品数量
        good[] A = new good[m+1];
        for(int i=1;i<=m;i++){
            strArr = br.readLine().split(" ");
            int v = Integer.parseInt(strArr[0]); //价格
            int p = Integer.parseInt(strArr[1]); //重要程度
            int q = Integer.parseInt(strArr[2]); //主附件（附件归属主件编号）
            if (flag){
                if(v%dw!=0){
                    flag = false;
                    dw=10;
                    //如果有物品没有到百元 则之前的物品乘10，所有物品按除10计算
                    for(int j=1;j<i;j++)
                        A[j].setV(A[j].v*10);
                }
            }
            v=v/dw;  //除100或10提升计算速度
            A[i]=new good(v,p,q);

        }

        for(int i=1;i<=m;i++){
            int q = A[i].q;
            if(q>0){
                //如果是附件的话 先判断是主件的第几个附件 再把附件对应的行数i赋给它 后面可以直接通过A[i]的a1、a2获取附件v、p
                if(A[q].a1==0){
                    A[q].setA1(i);
                }else{
                    A[q].setA2(i);
                }
            }
        }
        N=N/dw;
        dp(N,A);
    }
    public static void dp(int N, good[] A){
        int[][] dp = new int[N+1][A.length];

        for(int i=1;i<A.length;i++){
            int v=-1,v1=-1,v2=-1,v3=-1,tempdp=-1,tempdp1=-1,tempdp2=-1,tempdp3=-1;
            v=A[i].v;
            tempdp=v*A[i].p;
            if(A[i].a1!=0&&A[i].a2!=0){
                //通过A[i]的a1、a2获取附件v、p
                v3=v+A[A[i].a1].v+A[A[i].a2].v;
                tempdp3=tempdp+A[A[i].a1].v*A[A[i].a1].p+A[A[i].a2].v*A[A[i].a2].p;
            }
            if(A[i].a1!=0){
                v1 = v + A[A[i].a1].v;
                tempdp1=tempdp+A[A[i].a1].v*A[A[i].a1].p;
            }
            if(A[i].a2!=0){
                v2 = v + A[A[i].a2].v;
                tempdp2=tempdp+A[A[i].a2].v*A[A[i].a2].p;
            }
            for(int j=1;j<N+1;j++){
                if(A[i].q>0){
                    dp[j][i]=dp[j][i-1];
                }else{
                    dp[j][i]=dp[j][i-1];
                    //每组有四种情况:a.主件，b.主件+附件，c.主件+附件,d.主件+附件1+附件2
                    if(j>=v&&v!=-1) dp[j][i] = Math.max(dp[j][i],dp[j-v][i-1]+tempdp);
                    if(j>=v1&&v1!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v1][i-1]+tempdp1);
                    if(j>=v2&&v2!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v2][i-1]+tempdp2);
                    if(j>=v3&&v3!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v3][i-1]+tempdp3);
                }
            }

        }
        System.out.println(dp[N][A.length-1]*dw);
    }


}


class good{

    int v;
    int p;
    int q;
    int a1=0;
    int a2=0;

    good(int v,int p,int q){
        this.v=v;
        this.p=p;
        this.q=q;
    }
    public void setV(int v){
        this.v=v;
    }
    public void setA1(int a1){
        this.a1=a1;
    }
    public void setA2(int a2){
        this.a2=a2;
    }
}